/*#
 #*/
package cn.itaha.algorithm.leetcode.dynamicprogramming;

import java.util.ArrayList;
import java.util.List;
/**
 * <p>标题：三角形最小路径和</p>
 * <p>功能：</p>
 * <pre>
 * 其他说明：
 * 地址链接：https://leetcode-cn.com/problems/triangle/
 * </pre>
 * <p>创建日期：2019年11月26日上午10:02:26</p>
 * <p>类全名：cn.itaha.algorithm.leetcode.dynamicprogramming.Code120Triangle</p>
 * 查看帮助：<a href="" target="_blank"></a> 
 *
 * 作者：yinjun
 * 初审：
 * 复审：
 * @version 1.0
 */
public class Code120Triangle
{
	public static void main(String[] args)
	{
		/**
		 * 给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

		例如，给定三角形：

		[
		[2],
		[3,4],
		[6,5,7],
		[4,1,8,3]
		]
		自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

		说明：

		如果你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题，那么你的算法会很加分。
		 */
		List<List<Integer>> triangle = initParameters();
		int minimumTotal = minimumTotal(triangle);
		System.out.println(minimumTotal);
	}

	/**
	 * 本题采用动态规划思路:
	 * 		记三角形为数组S(java题中为集合，同理)
	 * 		由于自上往下来看，并非前一步的和最小，最终结果就最小，而是始终要考虑后面的值
	 * 		因此我们自下往上看：
	 * 			此时我们了解，每一步的和最小，则最终的结果就最小
	 * 		记dp[i,j]为坐标(i,j)上的路径最小和
	 * 		由题知道，这里的三角形是图形样式上的形状，因此所谓的相邻只有下层两个数
	 * 		则：
	 * 			dp[i,j] = min(S[i+1][j],S[i+1][j+1])+S[i,j]
	 * 		由于我们计算出坐标(i,j)位置上的结果后，就不再需要S(i,j),因此我们可以直接使用S[i,j]存储(i,j)上的最小和
	 * 		因此，我们直接循环两次给定数组或集合即可
	 * 
	 * 时间复杂度：O(n^2)
	 * 空间复杂度：O(1)
	 * 
	 * @param triangle
	 * @return
	 */
	public static int minimumTotal(List<List<Integer>> triangle)
	{
		//1.判断集合是否为空，为空则返回0
		if (triangle == null || triangle.isEmpty())
		{
			return 0;
		}
		//2.外层循环作为填值层，从倒数第二层开始，因为倒数第一层已经是路径终点
		for (int i = triangle.size() - 2; i >= 0; i--)
		{
			//3.取出第i+1层的数据集，作为取出原值计算，填充最小和用		注：因层数从1开始，集合从0开始，所以这里说为第i+1层,get(i)层,下面同理
			List<Integer> data = triangle.get(i);
			//4.取出第i+2层的数据集，最为值比较，取计算最小和的值
			List<Integer> dataFor = triangle.get(i + 1);
			//5.内层循环作取值比较出最小值，计算出i层每个元素所对应的最小和值
			for (int j = 0; j < data.size(); j++)
			{
				//6.取值比较取得是当前i的下一层的值
				int result = Math.min(dataFor.get(j), dataFor.get(j + 1));
				//7.计算和并设置值的是当前i层
				data.set(j, data.get(j) + result);
			}
		}
		//8.由于是自下往上计算，最终结果会汇总到顶层，因此取集合0号元素
		return triangle.get(0).get(0);
	}

	public static List<List<Integer>> initParameters()
	{
		List<List<Integer>> triangle = new ArrayList<List<Integer>>();
		List<Integer> triangleData1 = new ArrayList<Integer>();
		triangleData1.add(2);
		triangle.add(triangleData1);
		List<Integer> triangleData2 = new ArrayList<Integer>();
		triangleData2.add(3);
		triangleData2.add(4);
		triangle.add(triangleData2);
		List<Integer> triangleData3 = new ArrayList<Integer>();
		triangleData3.add(6);
		triangleData3.add(5);
		triangleData3.add(9);
		triangle.add(triangleData3);
		//		List<Integer> triangleData4 = new ArrayList<Integer>();
		//		triangleData4.add(4);
		//		triangleData4.add(4);
		//		triangleData4.add(8);
		//		triangleData4.add(0);
		//		triangle.add(triangleData4);
		return triangle;
	}
}
